/*
 * @Author: szx
 * @Date: 2022-03-24 14:43:58
 * @LastEditTime: 2022-03-24 15:03:07
 * @Description:
 * @FilePath: \leetcode\剑指offer\37\37.js
 */
function TreeNode(val) {
    this.val = val;
    this.left = this.right = null;
}

/**
 * Encodes a tree to a single string.
 *
 * @param {TreeNode} root
 * @return {string}
 */
var serialize = function (root) {
    if (!root) return [];
    const res = [];
    let que = [root];
    while (que.length) {
        const tmp_que = [];
        for (let i = 0; i < que.length; i++) {
            res.push(que[i].val);
            if (que[i].left) tmp_que.push(que[i].left);
            else res.push('#');
            if (que[i].right) tmp_que.push(que[i].right);
            else res.push('#');
        }
        que = tmp_que;
    }
    return res.join(',');
};

/**
 * Decodes your encoded data to tree.
 *
 * @param {string} data
 * @return {TreeNode}
 */
var deserialize = function (data) {
    if (!data) return null;
    const arr = data.split(',');
    const len = arr.length;
    let root = new TreeNode(arr[0]);
    const que = [root];
    let num = 1;
    while (num < len) {
        const node = que.shift();
        let leftVal = arr[num];
        let rightVal = arr[num + 1];
        if (leftVal !== '#') {
            node.left = new TreeNode(leftVal);
            que.push(node.left);
        }
        if (rightVal !== '#') {
            node.right = new TreeNode(rightVal);
            que.push(node.right);
        }
        num += 2;
    }
    return root;
};

/**
 * Your functions will be called as such:
 * deserialize(serialize(root));
 */
